CF906C Party

发布于 2020-09-17 | 分类于状压dp | 2分钟 | 353字数

首先预处理出一个人能介绍的人的集合 $rel$ 。（包括他本身）

令 $dp(S)$ 表示让集合 $S$ 中的人相互认识最少需要几个人。

那么可以刷表转移：

阅读全文 »

UVA1407 Caves

发布于 2020-09-12 | 分类于树形dp | 4分钟 | 730字数

一道标准的树形dp。

令 $dp[u][i][0/1]$ 表示以 $u$ 为根的子树，探索 $i$ 个洞穴，是否回到 $u$ 。

显然有：

阅读全文 »

CF815C Karen and Supermarket

发布于 2020-09-12 | 分类于树形dp | 4分钟 | 634字数

因为使用优惠劵就必须买这件商品，我们可以将优惠劵的关系看成一棵树。

令 $dp[u][i][0/1]$ 表示以 $u$ 为根的子树，购买 $i$ 件商品， $u$ 是否使用优惠劵的最小花费。

边界条件： $dp[u][0][0]=0,dp[u][1][0]=c[u],dp[u][1][1]=c[u]-d[u]$

阅读全文 »

P5176 公约数

发布于 2020-09-12 | 分类于莫比乌斯反演 | 15分钟 | 2336字数

首先有一个结论：

gcd(i\cdot j,i\cdot k,j\cdot k)=\frac{gcd(i , j )\cdot gcd(j , k) \cdot gcd(i,k)}{gcd(i,j,k)}

阅读全文 »

SP1026 FAVDICE - Favorite Dice

发布于 2020-09-12 | 分类于莫比乌斯反演 | 2分钟 | 302字数

令 $dp[i]$ 表示当前已经得到了 $i$ 个面后的期望次数。
有两种情况：

1.掷出已有的面，概率为 $\frac{i}{n}$

阅读全文 »

P4900 食堂

发布于 2020-09-12 | 分类于数学、数论 | 4分钟 | 576字数

题目需要求的是这个式子：

\sum_{i=A}^B\sum_{j=1}^i \{\frac{i}{j}\}

阅读全文 »

P3327 [SDOI2015]约数个数和

发布于 2020-09-12 | 分类于莫比乌斯反演 | 5分钟 | 744字数

首先有一个公式：

d(ij)=\sum_{x|i}\sum_{y|j}[(i,j)=1]

阅读全文 »

CF464D World of Darkraft - 2

发布于 2020-09-12 | 分类于概率dp | 3分钟 | 501字数

首先明确一点，所有装备的期望相同，只需求出任意一种后答案乘 $k$ 即可。

令 $dp[i][j]$ 表示还需要打 $i$ 只怪，装备等级为 $j$ 的金币数量期望。

那么有三种情况：

阅读全文 »

CF398B Painting The Wall

发布于 2020-09-12 | 分类于概率dp | 5分钟 | 833字数

先考虑所有格子均未涂色的情况。

因为格子的涂色只会影响一行一列，所以可以设 $dp(i,j)$ 表示还需要涂 $i$ 行， $j$ 列的期望步数。

1.涂色格所在行列均未染色，由 $dp(i-1,j-1)$ 转移，概率为 $\frac{i}{n} \times \frac{j}{n}$

阅读全文 »

P3501 [POI2010]ANT-Antisymmetry

发布于 2020-09-12 | 分类于回文自动机 | 2分钟 | 296字数

看到求回文串就想到 $\text{PAM}$ 。

因为只有 $0,1$ 所以判断条件改成等于。

不过这道题满足题意的串长度一定为偶，所以不能走到 $-1$ 根。

阅读全文 »